Communication systems utilize various types of error correction decoding methods for obtaining correct decoding results from data in which transmission errors have occurred. One decoding method for example possessing high error correction performance is known as the turbo decoding method and is disclosed by Yamaguchi and one other author, in the article “Near Shannon Limit Error—Correcting coding and decoding: Turbo-codes (1), Claude Berrou et al. Proc. IEEE 1993 (non-patent document 1). In the communications system shown in FIG. 1, the turbo coder 101 includes two recursive systematic convolutional coders 1 and 2 reference numerals 104 and 106, respectively. The convolutional coder 1 (104) encodes the signal from the information source in the order that it was input. Before being input to the convolutional coder 2 (106), the information source signals are accumulated temporarily in the memory, and are then extracted in sequence according to a pattern and their data sequence (signals) randomized by an interleaver (105) and then encoded by a convolutional coder 2 (106). The coded data U, Y0, Y1, Y2, Y3 from the two coded outputs are sent on a channel (102). The coded data U′, Y0, Y1′, Y2′, Y3′ is input by way of this channel (102) to the turbo decoder (103), and the decoded data U″ restored by decoding the turbo code.
The turbo decoder (103) includes decoders 1, 2 (107, 109) and, interleavers (108, 111) and deinterleavers (110, 112). In the decoder 1 (107), U′, Y0′, Y1′ equivalent to the transmit data U, Y0, Y1 is input and soft-decision decoding performed. Here, Y2′, Y3′ are equivalent to the transmit data Y2, Y3 from the interleaved and convolutional coded original signal X; the decoded data from the decoder 1 (107) is interleaved by the interleaver (108) so as to correspond to the Y2′, Y3′ and input to the decoder 2 (109), and soft-decision decoding performed. The output from the deinterleaver (110) that was deinterleaved to correspond to the original data sequence is once again input to the decoder 1 (107) as apriori likelihood (weight) information and the same operation repeated. The hard decision result output of the soft-decision decoding are deinterleaved by the deinterleaver (112) and acquired as the decoded output U″. Randomly occurring random errors and burst errors occurring in bursts can be corrected by repeating this decoding process multiple times. The decoders 1 and 2 are identical so in this embodiment so that in many cases during actual use, the decoders are used by alternately switching one decoder between a decoder 1 (for example used at even-numbered times) and a decoder 2 (for example used at odd-numbered times).
Typical decoding methods for the decoders 1, 2 are for example, the MAP (Maximum A Posteriori) decoding method and the SOVA (Soft Output Viterbi Algorithm) decoding method. The MAP decoding method calculates the forward path metric a and the backward path metric by utilizing the shift rate of the received data, and by using the forward path metric a and the backward path metric b over time (bit), finds the differential soft decision value versus that larger probability (hard decision value) finds of becoming a “1” or a “0”.
The SOVA decoding method is shown by Claude Berrou et al. in “A Low Complexity Soft-Output Viterbi Decoder Architecture”, Proc. IEEE, 1993 (non-patent document 2). A convolution coder conforming to 3GPP2 C. S0024-A and a trellis graph for that coder are shown in FIG. 2 using a convolutional coder as an example. When a signal is input to the decoder, tap state transitions in the convolution coder (201), and a state exists as 2^(k−1) when the constraint length is K. In FIG. 2, the convolutional coder K constraint length equals 4. When the tap state in FIG. 3, becomes 000, 001, 010, 011, 100, 101, 110, 111 then these are respectively defined as State 0, State 1, State 2, State 3, State 4, State 5, State 6, and State 7. When an input signal of 0 is input in the State 6, then a “001” is output as the convolutional output and the next State 7 is attained. When a bit=(−1) is input at the point in time of State 6, and a bit=0 is input at the point in time of State 7, then a transition from State 6 to State 7 occurs due to the input signal 0. The input signal string can be found by following the reverse of this transition state. Moving back through the transition states is called trace-back.
An overview of the trace-back operation in the SOVA decoding method is shown in FIG. 3. By first of all investigating the possibility of a transition change on a bit string from convolutional signals input to the decoder, up to Bit=(−N) in states where Bit=0 is State 1, Bit=(−1) is State 2, and Bit=(−2) is State 5, the bit string estimated to have been input can be output as a hard decision (solid line numerals on the path are estimated values) by the most likely survival path. When an error is assumed to have occurred in the estimate of the input signal from Bit=(−1) to Bit=0, then there may have been another transition shift so along with following the survival path, the transition shifts are investigated according to the survival path and reverse path information from Bit=(−1) to Bit=0, and this then followed (traced) as the concurrent path (dotted line). An operation generating a concurrent path is called a path branching. These branches are generated at each of the bits Bit=0, (−1), (−2), and path weight (path metric) information equivalent to the difference in likelihood versus the survival path is collected, and established as the soft decision value.
Making a trace-back of two paths (survival path and concurrent path) at once and comparing them in this way, requires two trace-back operations for establishing soft-decision results for 1 bit so that the calculation efficiency drops and time is required to establish all the soft decision outputs. A method was therefore proposed (JP-A No. 217748/2002) for performing trace-backs simultaneously on multiple paths by parallel trace-back circuit operation per the number of states to increase efficiency and achieve high-speed operation. The SOVA method only performs trace-back from the second likely path for each bit so that the error correction capability is essentially inferior to the MAP method that handles all paths but possesses the advantage of a small calculation load.
FIG. 4 however shows a method that generates branches even on concurrent paths for trace-back, to improve the error correcting capability even from the third likely path onward as described by Marc P. C. Fossorier, Frank Burkert, Shu Lin, Joachim Hagenauer: “On the Equivalence Between SOVA and Max-Log-MAP Decodings”, IEEE Communication Letters, vol. 2, pp. 137-139, May 1998 (non-patent document 3) (FIG. 4 is a graph for the operation of non-patent document 3.) Here, path-1 is the survival path, path-2, path-m are concurrent paths, and path-n is the branch from path-2 serving as a concurrent path. Paths uj different from uj1 are increased to account for the path-n, and by increasing potential paths, soft-decision output values are likely to have improved reliability. However, in this case, the number of branches from concurrent paths increase according to the length to where they merge with the survival path, so that there may be an enormous increase in the number of concurrent paths that must be traced at the same time.
[Non-patent document 1] “Near Shannon Limit Error—Correcting coding and decoding: Turbo-codes (1), Claude Berrou et al. Proc. IEEE 1993.
[Non-patent document 2] Claude Berrou et al., “A Low Complexity Soft-Output Viterbi Decoder Architecture”, Proc. IEEE, 1993.
[Non-patent document 3] Marc P. C. Fossorier, Frank Burkert, Shu Lin, Joachim Hagenauer: “On the Equivalence Between SOVA and Max-Log-MAP Decodings”, IEEE Communication Letters, vol. 2, pp. 137-139, May 1998.